/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-03
 * Time: 17:14
 */


import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * topk第一种
 * 自己写的
 * 没有利用优先级队列
 * 自己建堆
 */
public class TopK {
    public int[] getTopMinK(int[] array, int k) {
        if(k>array.length){
            return array;
        }
        int [] temp=new int[k];
        creatBigHeap(array,k);
        for (int i = 0; i < k; i++) {
            temp[i]=array[i];
        }
        return temp;
    }

    public void display(int [] array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }


    /**
     * 创建k大小的大堆
     * @param array
     * @param k
     */
    public void creatBigHeap(int[] array, int k) {
        int end=k-1;
        for (int i = (end-1)/2; i >=0; i--) {
            shiftDown(array,i,end);
        }
        for (int i = k; i < array.length; i++) {
            //如果小于堆顶元素就poll出去,将小的元素offer
            if(array[i]<array[0]){
                swap(array,0,end);
                shiftDown(array,0,end-1);
                array[end]=array[i];
                shiftUp(array,end);
            }
        }

    }

    /**
     * 向上调整
     */
    public void shiftUp(int [] array,int index){
        int child=index;
        int parent=(child-1)/2;
        while(parent>=0){
            if(array[parent]<array[child]){
                swap(array,child, parent);
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }


    /**
     * 向下调整
     * @param array
     * @param parent 要调整的元素的下标
     * @param end 要调整的结束位置
     */
    public void shiftDown(int []array,int parent,int end){
        int child=parent*2+1;
        if(child>end){
            return;
        }
        while(child<=end){
            if(child+1<=end&&array[child+1]>array[child]){
                child++;
            }
            if(array[parent]<array[child]){
                swap(array,parent,child);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }

    public void swap(int [] array,int index1,int index2){
        int temp=array[index1];
        array[index1]=array[index2];
        array[index2]=temp;
    }
}

/**
 * topK第二种
 * 利用优先级队列
 */
class TopMinK {
    public int [] topK(int[] array, int k) {
        if(k>=array.length){
            return array;
        }
        //一:先建大堆
        PriorityQueue<Integer> maxHeap=creatbigHeap(array,k);
        //二:开始找最小的K个元素
            //小于k个元素时直接入队
        for (int i = 0; i < k; i++) {
            maxHeap.offer(array[i]);
        }
            //大于K个元素开始比较
        for (int i = k; i < array.length; i++) {
            if(array[i]<maxHeap.peek()){
                maxHeap.poll();
                maxHeap.offer(array[i]);
            }
        }

        int [] temp=new int[k];
        for (int i = 0; i < k; i++) {
            temp[i]=maxHeap.poll();
        }
        return temp;
    }

    public PriorityQueue<Integer>  creatbigHeap(int[] array, int k) {
        //匿名内部类
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        return priorityQueue;
    }
}